package learn_03_01;


import java.util.*;

public class string_question {
        public static List<List<String>> groupAnagrams(String[] strs) {
            Map<String,List<String>> strsMap = new HashMap();
            for(String s : strs) {
                String sort_s = getSort(s);
                if(!strsMap.containsKey(sort_s)){
                    List<String> s_list = new ArrayList();
                    s_list.add(s);
                    strsMap.put(sort_s,s_list);
                }else{
                    List<String> s_list =strsMap.get(sort_s);
                    s_list.add(s);
                }
            }
            List result = new ArrayList();
            for (String key : strsMap.keySet()) {
                result.add(strsMap.get(key));
            }
            return result;
        }

        private static String getSort(String s){
            if(s.length()==0){
                return s ;
            }
            char[] chars = s.toCharArray();
            //应用插入排序
            for(int i = 1;i<chars.length;i++){
                char now = s.charAt(i);
                int j = i;
                while( j>=1 && now>chars[j-1]){
                    chars[j] = chars[j-1];
                    j--;
                }
                chars[j] = now;
            }
            return new String(chars);
        }

    public static void main(String[] args) {
        String[] fruits = {"eat", "tea", "tan", "ate", "nat", "bat"};
        List result = groupAnagrams(fruits);
        System.out.print(result);
    }

}
